package BinaryTree.Medium;

import DataStructures.TreeNode;

import java.util.HashMap;

public class LC0105 {
    HashMap<Integer, Integer> numberIdxMapInorder = new HashMap<>(); // 结点值到inorder数组索引的映射
    HashMap<Integer, Integer> numberIdxMapPreorder = new HashMap<>(); // 结点值到preorder数组索引的映射
    int N;

    int[][] minPreorderIdx, maxPreorderIdx;

    /**
     * 从前序遍历和中序遍历构造二叉树，存在标准的算法。本题的关键是，如何高效地确定一个子树所包含的元素，在preorder和inorder数组中的索引范围。
     * 假设我们有preorder的一段，以及inorder的一段，上述问题，就是要确定左右子树在inorder和preorder中分别对应哪一段。
     * 最直接的想法是，先找到preorder[0]（根）在inorder中的位置，这样可以确定inorder左右两段的范围；然后遍历inorder的左右两段，来确定这两段
     * 在preorder中的范围。
     * 显然，这种做法会导致大量的重复计算。因此，这种解法使用动态规划的方法预先存储了inorder中的一段映射到preorder后的范围。
     * 时间复杂度：N^2
     * 空间复杂度：N^2
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        N = preorder.length;
        for (int i = 0; i < N; i++) {
            numberIdxMapInorder.put(inorder[i], i);
            numberIdxMapPreorder.put(preorder[i], i);
        }

        minPreorderIdx = new int[N][N]; // m[i,j]表示inorder数组中[i,j]范围内的各个数字，在preorder中索引最小的一个。j必须大于i。
        maxPreorderIdx = new int[N][N];
        for (int i = 0; i < N; i++) {
            minPreorderIdx[i][i] = numberIdxMapPreorder.get(inorder[i]);
            maxPreorderIdx[i][i] = numberIdxMapPreorder.get(inorder[i]);
        }

        for (int i = 0; i < N - 1; i++) {
            for (int delta = 1; delta <= N - 1 - i; delta++) {
                int j = i + delta;
                // 新加入的索引是否比以前的任何一个索引更小
                minPreorderIdx[i][j] = Math.min(minPreorderIdx[i][j - 1], numberIdxMapPreorder.get(inorder[j]));
                maxPreorderIdx[i][j] = Math.max(maxPreorderIdx[i][j - 1], numberIdxMapPreorder.get(inorder[j]));
            }
        }

        return innerRecursive(preorder, inorder, 0, N, 0, N);
    }

    private TreeNode innerRecursive(int[] preorder, int[] inorder, int preorderStart, int preorderEnd,
                                    int inorderStart, int inorderEnd) {
        if (preorderStart >= N || preorderEnd < 0 || inorderStart >= N || inorderEnd < 0) return null;
        int nNodes = preorderEnd - preorderStart;

        TreeNode root = new TreeNode(preorder[preorderStart]);
        if (nNodes <= 2) {
            if (nNodes == 2) {
                if (preorder[preorderStart] == inorder[inorderStart]) { // 另一结点在右侧
                    root.right = new TreeNode(inorder[inorderEnd - 1]);
                }
                else { // 另一结点在左侧
                    root.left = new TreeNode(preorder[preorderEnd - 1]);
                }
            }

            return root;
        }

        // 子树结点数至少为3，递归
        int rootInorderIdx = numberIdxMapInorder.get(root.val);
        int inorderLeftStart = inorderStart, inorderLeftEnd = rootInorderIdx;
        int inorderRightStart = rootInorderIdx + 1, inorderRightEnd = inorderEnd;
        if (inorderLeftEnd > inorderLeftStart) {
            int preorderLeftStart = minPreorderIdx[inorderLeftStart][inorderLeftEnd - 1],
                    preorderLeftEnd = maxPreorderIdx[inorderLeftStart][inorderLeftEnd - 1];
            root.left = innerRecursive(preorder, inorder, preorderLeftStart, preorderLeftEnd + 1, inorderLeftStart, inorderLeftEnd);
        }
        if (inorderRightEnd > inorderRightStart) {
            int preorderRightStart = minPreorderIdx[inorderRightStart][inorderRightEnd - 1],
                    preorderRightEnd = maxPreorderIdx[inorderRightStart][inorderRightEnd - 1];
            root.right = innerRecursive(preorder, inorder, preorderRightStart, preorderRightEnd + 1, inorderRightStart, inorderRightEnd);
        }

        return root;
    }

    /**
     * 先前那种解法的问题在于忽略了这样一个性质，即preorder数组在根后一定紧接着代表左子树和右子树的两段，如果能知道左右子树的尺寸，就可以快速地区分出这两段；
     * 而左右子树的尺寸可以通过inorder快速地得知：一旦知道了根在inorder中的位置，那么左边一段就是左子树，右边一段就是右子树。
     */
    public TreeNode buildTreeOptimized(int[] preorder, int[] inorder) {
        N = preorder.length;
        for (int i = 0; i < N; i++) {
            numberIdxMapInorder.put(inorder[i], i);
            numberIdxMapPreorder.put(preorder[i], i);
        }

        return innerRecursive2(preorder, inorder, 0, N, 0, N);
    }

    private TreeNode innerRecursive2(int[] preorder, int[] inorder, int preorderStart, int preorderEnd,
                                     int inorderStart, int inorderEnd) {
        if (preorderStart >= N || preorderEnd < 0 || inorderStart >= N || inorderEnd < 0) return null;
        int nNodes = preorderEnd - preorderStart;

        TreeNode root = new TreeNode(preorder[preorderStart]);
        if (nNodes <= 2) {
            if (nNodes == 2) {
                if (preorder[preorderStart] == inorder[inorderStart]) { // 另一结点在右侧
                    root.right = new TreeNode(inorder[inorderEnd - 1]);
                }
                else { // 另一结点在左侧
                    root.left = new TreeNode(preorder[preorderEnd - 1]);
                }
            }

            return root;
        }

        // 子树结点数至少为3，递归
        int rootInorderIdx = numberIdxMapInorder.get(root.val);
        int inorderLeftStart = inorderStart, inorderLeftEnd = rootInorderIdx;
        int inorderRightStart = rootInorderIdx + 1, inorderRightEnd = inorderEnd;
        int leftTreeSize = inorderLeftEnd - inorderLeftStart, rightTreeSize = inorderRightEnd - inorderRightStart;
        if (leftTreeSize >= 1) {
            int preorderLeftStart = preorderStart + 1,
                    preorderLeftEnd = preorderLeftStart + leftTreeSize;
            root.left = innerRecursive2(preorder, inorder, preorderLeftStart, preorderLeftEnd, inorderLeftStart, inorderLeftEnd);
        }
        if (rightTreeSize >= 1) {
            int preorderRightEnd = preorderEnd,
                    preorderRightStart = preorderRightEnd - rightTreeSize;
            root.right = innerRecursive2(preorder, inorder, preorderRightStart, preorderRightEnd, inorderRightStart, inorderRightEnd);
        }

        return root;
    }

    public static void main(String[] args) {
        int[] preorder = new int[]{3, 9, 20, 15, 7};
        int[] inorder = new int[]{9, 3, 15, 20, 7};
        LC0105 solver = new LC0105();
        solver.buildTreeOptimized(preorder, inorder);
    }
}
